package com.zklh.leetcode.top100;

/**
 * 接雨水算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/17
 */
public class Solution42 {
    public int trap(int[] height) {
        int left = 0, right;
        int total = 0;
        int highest = height.length-1;
        while (left < height.length-1) {
            int areaSum = 0;
            right = left + 1;
            while (right < height.length && height[right] < height[left]) right++;
            if (right == height.length) {
                highest = left;
                break;
            }
            int temp = left+1;
            while (temp < right) {
                areaSum += height[left] - height[temp++];
            }
            total += areaSum;
            left = right;
        }

        left = height.length - 1;
        right = height.length-1;
        while (right > highest) {
            left = right - 1;
            while (left >= highest && height[left] < height[right]) left--;
            int temp = left + 1;
            int areaSum = 0;
            while (temp < right) {
                areaSum += height[right] - height[temp++];
            }
            total += areaSum;
            right = left;
        }

        return total;
    }

    public static void main(String[] args) {
        Solution42 solution42 = new Solution42();
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        // int[] height = {4,2,0,3,2,5};
        System.out.println(solution42.trap(height));
    }
}